package protect.week08;


/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/20 14:48
 * @package protect.week08
 * @description 509. 斐波那契数
 * 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
 *
 * F(0) = 0，F(1) = 1
 * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 * 给定 n ，请计算 F(n) 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：1
 * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：2
 * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
 * 示例 3：
 *
 * 输入：n = 4
 * 输出：3
 * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/fibonacci-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Ch03_Fib {
    public int fib(int n) {
        // 如果 n  < = 1 时候，直接返回 n
        if(n <=1){
            return n;
        }

        // 当 n  > 1 时，建立一个新的数组，并用斐波那契
        int[] fib = new int[n+1];
        fib[0]=0;
        fib[1] =1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i-1] +fib[i-2];
        }

        return fib[n];
    }
}